package demo;
import java.util.Arrays;

//二叉树向下调整，堆化
public class HeapOperation {
    //二叉树堆化，此处是最大根堆
    public static void shiftDown(long[]array,int size,int index){
      while(true){
          int leftIdx=2*index+1;
          //如果已经是叶子，那么不需要再调整
          if(leftIdx>=size){
              //完全堆化直接退出
              return;
          }
          //假设左孩子最大
          int maxIdx=leftIdx;
         //当左右孩子都有时，并且右孩子大于左孩子，假设不成立
          if(leftIdx+1<size&&array[leftIdx+1]>array[leftIdx]){
              maxIdx=leftIdx+1;
          }
          //求出左右孩子里最大的之后与要调整位置比较，判断是否堆化

          if(array[index]>=array[maxIdx]){
              //若要调整位置已经是最大，直接退出
              return;
          }
          //把要调整位置与左右孩子的最大交换元素
          long temp=array[index];
          array[index]=array[maxIdx];
          array[maxIdx]=temp;
          //把最大孩子下标交给要调整位置
          index=maxIdx;
      }
    }

    //二叉树堆化，此是最小根堆
    public static void shiftDown2(long []array,int size,int index){
        while(true){
            //左子树下标
            int leftIdx=2*index+1;
            //如果已经是叶子则不用再堆化
            if(leftIdx>=size){
                return;
            }
            //接下来要找左右孩子里哪个最小
            //假设左孩子是左右孩子里最小的
            int minIdx=leftIdx;
            //当有右孩子且右孩子小于左孩子时不成立
            if(leftIdx+1<size&&array[leftIdx+1]<array[leftIdx]){
                minIdx=leftIdx+1;
            }
            //找出左右孩子哪个最小后与最小孩子比较判断是否完全堆化
            if(array[index]<=array[minIdx]){
                //调整位置已经小于最小孩子 已经最小完全堆化，直接退出
                return ;
            }

            //否则需要交换调整位置与最小孩子的元素与下标

            long temp=array[index];
            array[index]=array[minIdx];
            array[minIdx]=temp;

            //交换下标
            index=minIdx;
        }

    }

    public static void main(String[] args) {

        long[]array2={27,15,19,18,28,34,65,49,25,37};
        int index=0;
        System.out.println("堆化前：");
        System.out.println(Arrays.toString(array2));
        System.out.println("堆化后：");
        shiftDown2(array2,10,index);
        System.out.println(Arrays.toString(array2));

        long[]array={5,3,5,5,5,5,5,5,5,0,0,0,0};
         index=1;
        System.out.println("堆化前：");
        System.out.println(Arrays.toString(array));
        System.out.println("堆化后：");
        shiftDown(array,9,index);
        System.out.println(Arrays.toString(array));






    }







}
